Parallel computer programs are fundamentally more difficult to validate, test, and debug than sequential computer programs. While typical programs can exhibit traditional "sequential" errors, such as those caused by incorrect syntax, program logic, control flow, or rounding or truncation of numerical results, parallel programs can exhibit additional types of errors. Parallel programming errors can result from parallelizing a sequential program, wherein constraints on the ordering of operations in the original sequential program are relaxed in order to exploit parallelism, which results in unintended indeterminacy. In addition, errors can result from the incorrect application or use of parallel programming constructs; many of these errors are difficult or impossible to detect statically, especially without employing interprocedural analysis.
In many common parallel programming languages, a parallel program is constructed by starting with a sequential program and then forming its corresponding parallel version by annotating the sequential program, for example, with directives or language-extension statements. The traditional view of these annotations has been that they describe parallel programming constructs to be added to the sequential program. An alternative view, however, is that such annotations describe constraints in the sequential program to be relaxed to allow the exploitation of parallelism. This alternative view facilitates a broad definition of parallel program validation, wherein a parallel program is validated for correctness with respect to its corresponding sequential program, independent of timing, scheduling, or the number of processors or threads used to execute the parallel program. Validation should consider semantic inconsistencies caused by the incorrect use of parallel programming constructs as well as by unintended indeterminacy. Such semantic inconsistencies include not only dynamic dependencies but other errors caused by the modification of the sequential program.
The prior art has largely taken the traditional view in addressing parallel program debugging. Race detection and dynamic dependence analysis schemes have been described that detect errors caused by unintended indeterminacy during parallel execution. Little prior art exists, however, with respect to detecting errors caused by the incorrect use of parallel programming constructs or with respect to the general problem of parallel program validation as defined above.
Race detection schemes employ either static, post-mortem, and on-the-fly analysis methods. Static methods suffer the disadvantage of being overly conservative, even if aggressive interprocedural and symbolic analysis is used, since they do not resolve references that must be analyzed at runtime. Post-mortem methods require the production and storage of extremely large amounts of data in order to provide complete, accurate race analysis. Reducing the amount of data required results in correspondingly less accurate analysis. On-the-fly race analysis methods help eliminate the requirement of storing large amounts of post-mortem analysis data, without sacrificing the accuracy of dynamic analysis techniques. Most race detection schemes, however, require a parallel execution of the program being analyzed. These methods typically require a (particular) parallel machine on which to execute the parallel program, and thus can not analyze parallel programs with severe errors that prevent parallel execution or cause abnormal termination.
Dynamic dependence analysis methods detect data races that could potentially occur during execution of a parallel program via on-the-fly analysis of the corresponding sequential program. These methods do not require parallel execution, and they isolate the analysis from particular timings or interleavings of events, scheduling methods, or numbers of processors or threads used. Dynamic dependence analysis schemes, however, do not detect errors arising from incorrect parallel programming construct use, and do not fully support a complete parallel programming language or dialect.
Most race detection schemes, even those employing so-called sequential traces, are limited in several ways. First, they suffer all the disadvantages of dynamic methods that require parallel execution: the schemes are inherently less portable, and they cannot analyze parallel programs with catastrophic errors. Second, many of these schemes assume simplified parallel programming models, and most are not based on realistic, complete parallel programming languages or dialects. While these schemes address the issue of language generality, they still suffer the disadvantage of requiring parallel execution, which limits the classes of errors that can be analyzed, and the portability and applicability of the methods.
Other relative debugging techniques also suffer the disadvantages of most of the aforementioned schemes (e.g., requiring parallel execution, analyzing one particular parallel execution). Some degree of parallel execution is still required. The prior art, therefore, lacks the advantage of validating the correctness of a parallel computer program without the need for parallel execution.